


//https://leetcode.cn/problems/permutations/?envType=study-plan-v2&envId=top-100-liked

//重点！！！
//思想：dfs + set容器实现：实现字符串的

#include <string>
#include <vector>
#include <set>

using namespace std;

class Solution {
public:
    void dfs(int loc, vector<int>& s, set<vector<int>>& ans) {
        if (loc == s.size() - 1) { //递归边界
            ans.insert(s);//找到一个排序，并且插入
            return ;
        }
        for (int i = loc; i < s.size(); i++) { //假设原来的元素映射到他的下标，那么我们搜索的是下标的全排序
            swap(s[i], s[loc]);
            dfs(loc + 1, s, ans); //进入下一层递归
            swap(s[i], s[loc]); //还原s
        }
    }
    vector<vector<int>> permute(vector<int>& nums) {
        if(nums.empty()) return {};
        set<vector<int>> ans;
        dfs(0, nums, ans); //开始搜索字符串
        return vector<vector<int>>(ans.begin(), ans.end()); 
    }
};